/**
 * @file   1098.cpp
 * @author Shuang Hu <hsmath@ubuntu>
 * @date   Thu Jul 29 19:05:42 2021
 * 
 * @brief  PAT advanced 1098:Insertion?Heap?
 * 
 * 
 */
#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<algorithm>
using namespace std;
class Solution{
private:
    vector<int> arr1;
    vector<int> arr2;
    int size;
    int type;
    int flag;
public:
    Solution();
    void judge();
    void solve();
    void print();
};
void percdown(vector<int>& arr,int from,int to){
    int i=from;
    while(i<=to){
	int tmp=i;
	tmp=tmp*2;
	if((tmp+1)<=to&&arr[tmp+1]>arr[tmp]){
	    tmp++;
	}
	if(arr[tmp]<arr[i]){
	    break;
	}else{
	    swap(arr[tmp],arr[i]);
	    i=tmp;
	}
    }
    return;
}
Solution::Solution(){
    cin>>size;
    arr1.resize(size+1);
    arr2.resize(size+1);
    for(int i=1;i<=size;i++){
	cin>>arr1[i];
    }
    for(int i=1;i<=size;i++){
	cin>>arr2[i];
    }
    type=0;
    flag=0;
}
void Solution::judge(){
    flag=1;
    for(int i=2;i<=size;i++){
	if(arr2[i]<arr2[i-1]){
	    flag=i;
	    break;
	}
    }
    type=1;
    for(int j=flag;j<=size;j++){
	if(arr1[j]!=arr2[j]){
	    type=2;//Heap Sort!
	    break;
	}
    }
}
void Solution::solve(){
    if(type==1){
	cout<<"Insertion Sort"<<endl;
	sort(arr2.begin()+1,arr2.begin()+flag+1);
	return;
    }else{
	cout<<"Heap Sort"<<endl;
	flag=size;
	for(flag=size;flag>=1;flag--){
	    if(arr2[flag]<arr2[1]){
		break;
	    }
	}
	swap(arr2[1],arr2[flag]);
	percdown(arr2,1,flag-1);
    }
}
void Solution::print(){
    cout<<arr2[1];
    for(int i=2;i<=size;i++){
	cout<<" "<<arr2[i];
    }
    cout<<endl;
}
int main(){
    Solution S;
    S.judge();
    S.solve();
    S.print();
}
